#
# @lc app=leetcode.cn id=63 lang=python3
#
# [63] 不同路径 II
#

# @lc code=start
from typing import List

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        
        pathsCount = [0] * n        # 这里不是m，是n
        index = n - 1
        while index >= 0:
            if obstacleGrid[m-1][index] == 0:
                pathsCount[index] = 1
            else:
                break
            index -= 1
                
        for i in reversed(range(0, m - 1)):
            # 最后一列的计算，如果有一个位置有障碍，那么这条路就不通了
            if obstacleGrid[i][n - 1] == 1:
                pathsCount[n-1] = 0
            
            for j in reversed(range(0, n - 1)):
                if obstacleGrid[i][j] == 1:
                    pathsCount[j] = 0
                else:
                    pathsCount[j] = pathsCount[j+1] + pathsCount[j]
                    
        return pathsCount[0]
# Solution().uniquePathsWithObstacles([[0,0],[0,1]])       
# @lc code=end

